#include "aatree.h"
#include <stdlib.h>
#include "fatal.h"

/* START: fig12_27.txt */
/* Returned for failures */
Position NullNode = NULL;  /* Needs more initialization */

struct AANode
{
    ElementType Element;
    AATree      Left;
    AATree      Right;
    int         Level;
};

AATree
Initialize( void )
{
    if( NullNode == NULL )
    {
        NullNode = malloc( sizeof( struct AANode ) );
        if( NullNode == NULL )
            FatalError( "Out of space!!!" );
        NullNode->Left = NullNode->Right = NullNode;
        NullNode->Level = 0;
    }
    return NullNode;
}
/* END */

AATree
MakeEmpty( AATree T )
{
    if( T != NullNode )
    {
        MakeEmpty( T->Left );
        MakeEmpty( T->Right );
        free( T );
    }
    return NullNode;
}

Position
Find( ElementType X, AATree T )
{
    if( T == NullNode )
        return NullNode;
    if( X < T->Element )
        return Find( X, T->Left );
    else
    if( X > T->Element )
        return Find( X, T->Right );
    else
        return T;
}

Position
FindMin( AATree T )
{
    if( T == NullNode )
        return NullNode;
    else
    if( T->Left == NullNode )
        return T;
    else
        return FindMin( T->Left );
}

Position
FindMax( AATree T )
{
    if( T != NullNode )
        while( T->Right != NullNode )
            T = T->Right;

    return T;
}

/* This function can be called only if K2 has a left child */
/* Perform a rotate between a node (K2) and its left child */
/* Update heights, then return new root */

static Position
SingleRotateWithLeft( Position K2 )
{
    Position K1;

    K1 = K2->Left;
    K2->Left = K1->Right;
    K1->Right = K2;

    return K1;  /* New root */
}

/* This function can be called only if K1 has a right child */
/* Perform a rotate between a node (K1) and its right child */
/* Update heights, then return new root */

static Position
SingleRotateWithRight( Position K1 )
{
    Position K2;

    K2 = K1->Right;
    K1->Right = K2->Left;
    K2->Left = K1;

    return K2;  /* New root */
}

/* START: fig12_29.txt */
/* If T's left child is on the same level as T, */
/* perform a rotation */

AATree
Skew( AATree T )
{
    if( T->Left->Level == T->Level )
        T = SingleRotateWithLeft( T );
    return T;
}

/* If T's rightmost grandchild is on the same level, */
/* rotate right child up */

AATree
Split( AATree T )
{
    if( T->Right->Right->Level == T->Level )
    {
        T = SingleRotateWithRight( T );
        T->Level++;
    }
    return T;
}
/* END */

/* START: fig12_36.txt */
AATree
Insert( ElementType Item, AATree T )
{
    if( T == NullNode )
    {
        /* Create and return a one-node tree */
        T = malloc( sizeof( struct AANode ) );
        if( T == NULL )
            FatalError( "Out of space!!!" );
        else
        {
            T->Element = Item; T->Level = 1;
            T->Left = T->Right = NullNode;
        }
    }
    else
    if( Item < T->Element )
        T->Left = Insert( Item, T->Left );
    else
    if( Item > T->Element )
        T->Right = Insert( Item, T->Right );

    /* Otherwise it's a duplicate; do nothing */

    T = Skew( T );
    T = Split( T );
    return T;
}
/* END */

/* START: fig12_38.txt */
AATree
Remove( ElementType Item, AATree T )
{
    static Position DeletePtr, LastPtr;

    if( T != NullNode )
    {
        /* Step 1: Search down tree */
        /*         set LastPtr and DeletePtr */
        LastPtr = T;
        if( Item < T->Element )
            T->Left = Remove( Item, T->Left );
        else
        {
            DeletePtr = T;
            T->Right = Remove( Item, T->Right );
        }

        /* Step 2: If at the bottom of the tree and */
        /*         item is present, we remove it */
        if( T == LastPtr )
        {
            if( DeletePtr != NullNode &&
                     Item == DeletePtr->Element )
            {
                DeletePtr->Element = T->Element;
                DeletePtr = NullNode;
                T = T->Right;
                free( LastPtr );
            }
        }

        /* Step 3: Otherwise, we are not at the bottom; */
        /*         rebalance */
        else
            if( T->Left->Level < T->Level - 1 ||
                T->Right->Level < T->Level - 1 )
            {
                if( T->Right->Level > --T->Level )
                    T->Right->Level = T->Level;
                T = Skew( T );
                T->Right = Skew( T->Right );
                T->Right->Right = Skew( T->Right->Right );
                T = Split( T );
                T->Right = Split( T->Right );
            }
    }
    return T;
}
/* END */

ElementType
Retrieve( Position P )
{
    return P->Element;
}
